/**
 * 带头尾指针的链表，实现队列
 *      实现方便的出队和入队,时间复杂度:O(1)
 */
public class LinkedListQueue<T> implements Queue<T>{

    private class Node{
        private T t;
        private Node next;

        public Node(T t,Node next){
            this.t = t;
            this.next = next;
        }

        public Node(T t){
            this(t,null);
        }

        public Node(){
            this(null,null);
        }

        @Override
        public String toString(){
            return t.toString();
        }
    }

    private Node head,tail;
    private int size;

    public LinkedListQueue(){
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public void enqueue(T t) {
        if(tail == null){
            tail = new Node(t);
            head = tail;
        }else {
            tail.next = new Node(t);
            tail = tail.next;
        }
        size ++;
    }

    @Override
    public T dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("Queue is empty,cannot dequeue");
        }
        Node retNode = head;
        head = head.next;
        retNode.next = null;

        size --;
        return retNode.t;
    }

    @Override
    public T getFront() {
        return head.t;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for(Node cur = head;cur != null;cur =cur.next){
            res.append(cur + "->");
        }
        res.append("Null] tail");
        return res.toString();
    }

    public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        for (int i=0;i<10;i++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i%3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}
